# LeetCode 139、单词拆分
# 一、题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅有小写英文字母组成wordDict中的所有字符串 互不相同
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 单词拆分（LeetCode 139）：https://leetcode.cn/problems/word-break/submissions/
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// wordDict 可能包含重复的字符串，采取一个去重的操作
Set<String> wordDictSet = new HashSet(wordDict);
// dp[i] 表示 s 的前 i 位是否可以用 wordDict 中的单词表示
boolean[] dp = new boolean[s.length() + 1];
// 一个空字符可以用 wordDict 中的单词表示
dp[0] = true;
// 一个优化的方案：先去获取 wordDict 最长字符的长度
int maxWordLength = 0;
// 先去获取 wordDict 最长字符的长度
for( int i = 0 ; i < wordDict.size() ; i++){
String word = wordDict.get(i);
maxWordLength = Math.max(maxWordLength , word.length());
}
// 开始填充 dp 数组
// 遍历字符串的所有子串
for( int i = 1 ; i <= s.length() ; i++){
// 在遍历过程中，获取 s 中的子串
// 判断 s( 0 , i ) 能否用 wordDict 中的单词表示
// s( 0 , i ) 可以划分为两个部分 s( 0 , j ) 和 s( j , i )
// 如果发现 ( 0 , j )可以用 wordDict 中的单词表示
// 同时，wordDictSet 还包含了 s( j , i )，那说明 s( 0 , i ) 能否用 wordDict 中的单词表示
// 这里采取了一个优化，极大提高了计算效率
// j 不需要每次都从 0 开始，可以直接提前到距离 i 差 maxWordLength 个字符的位置
// 因为 wordDict 中最长字符的长度是 maxWordLength
// 那么 j 从 i - maxWordLength 开始 s( j , i ) 不会忽略掉判断这个最长字符
// 并且在 i < maxWordLength 这个阶段， index 依旧是从 0 开始，涵盖了 s( 0 , i - maxWordLength )这些子串的判断
int index = Math.max( i - maxWordLength , 0 );
// j 不需要每次都从 0 开始，可以直接提前到距离 i 差 maxWordLength 个字符的位置
// 接下来的核心点就是判断 s( j , i ) 是否可以被构成一个单词
for(int j = index ; j < i ; j++ ){
// 1、如果发现 s 的前 j 位是否可以用 wordDict 中的单词表示
// 2、wordDict 还包含了 s.substring(j , i ) 这个子串
// 即 s 中的前部分 ( 0 , j ) 可以被表示
// s 中的后部分 ( j , i ) 也可以被表示
// 那么子串 s ( 0 , i ) 可以被表示
if(dp[j] && wordDictSet.contains(s.substring(j , i ))){
// 即 s 的前 i 位可以用 wordDict 中的单词表示
dp[i] = true;
// 那么 j 也就没有必要继续执行 ++ 操作了
break;
}
}
}
return dp[s.length()];
}
}